package com.mlh.dp.knapsackProblem;

// 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
// 完全平方数 是一个整数，其值等于另一个整数的平方；
// 换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是
// 输入：n = 12
// 输出：3
// 解释：12 = 4 + 4 + 4

// 输入：n = 13
// 输出：2
// 解释：13 = 4 + 9

import java.util.Arrays;
import java.util.Iterator;

//未作出 看题解
public class NumSquares {

    public static void main(String[] args) {
        method1(12);
    }


    //其实这题挺简单的  当时没想出来 确实可惜
    //思路就很简单
    //动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i 表示当前数字，j*j 表示平方数
    public static int method1(int n){
        int[]dp=new int[n+1];
        for(int i=1;i<n+1;i++){
            int res= Integer.MAX_VALUE;
            for(int j=1;i-j*j>=0;j++){
                res=Math.min(res,dp[i-j*j]+1);
            }
            dp[i]=res;
        }
        return dp[n];
    }
}
